package Sequence;

public class Test0450 {
    public static void main(String[] args) {
        new Solution0450_1().deleteNode(new TreeNode(5,new TreeNode(3),new TreeNode(6)),3);
    }
}

class Solution0450_1 {
    public TreeNode deleteNode (TreeNode root, int key) {
        if (root==null) {
            return null;
        }
        TreeNode pre = new TreeNode(root.val,root,root);
        TreeNode search = search(pre, key);
        if (search==null){
            return root;
        }

        if (search.val>key){
            search.left=build(search.left);
        }else {
            search.right=build(search.right);
        }

        return pre.right;
    }

    public TreeNode search(TreeNode root, int key){
        if (root==null) {
            return null;
        }
        int val = root.val;
        TreeNode left = root.left;
        TreeNode right = root.right;
        if ((left!=null&&left.val==key)||(right!=null&&right.val==key)) {
            return root;
        }

        if (key< val){
            return search(left,key);
        }else {
            return search(right,key);
        }
    }

    public TreeNode build(TreeNode root){
        if (root.left==null||root.right==null) {
            return root.left!=null?root.left:root.right;
        }

        TreeNode temp = root.left;
        while (temp.right!=null) {
            temp=temp.right;
        }

        temp.right=root.right;
        return root.left;
    }
}
